/*
 * Result.h
 *
 *  Created on: Mar 9, 2017
 *      Author: along
 */

#ifndef RESULT_H_
#define RESULT_H_

#include "Graph.h"
#include "my_io.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <sstream>
#include <string>
#include <stdexcept>

using namespace std;

class Result
{
private:
	Graph deployment;
	int size_g;
	vector<int> pre,dis;
	vector<bool> vis;
	vector<vector<int> > roads;
	map<int,int> consumers_id;
public:
	Result(){}
	Result(Graph g,vector<Consumer> consumers)
	{
		size_g = g.size();
		pre.resize(size_g);
		dis.resize(size_g);
		vis.resize(size_g);
		deployment = Graph(size_g);
		int len = consumers.size();
		for(int i=0;i<len;++i)
		{
			consumers_id[consumers[i].id_g] = consumers[i].id;
		}
		transform(g);
	}
	
	void transform(Graph& g)
	{
		vector<Edge> e_g = g.get_all_edges();
		int len = e_g.size();
		for(int i = 0;i < len;++i)
		{
			Edge e_t = e_g[i];
#ifdef _LOCAL_DEBUG
			if(e_t.flow > e_t.cap)
			{
				throw runtime_error("e_t.flow > e_t.cap in Result.transform\n");
			}
#endif
			e_t.cap = e_t.flow;
			e_t.flow = 0;
			deployment.insert_edge(e_t);
		}
	}

	Graph get_deployment()
	{
		return deployment;
	}

	bool spfa(int s,int t)
	{
		queue<int> q;
		for(int i=0;i<size_g;++i)
		{
			dis[i] = INF;
			vis[i] = false;
			pre[i] = -1;
		}
		dis[s] = 0;
		vis[s] = true;
		q.push(s);
		while(!q.empty())
		{
			int from = q.front();
			q.pop();
			vis[from] = false;
			vector<Edge> e = deployment.get_edges(from);
			int len = e.size();
			for(int i = 0;i < len;++i)
			{
				int to = e[i].to;
				if(e[i].cap > e[i].flow && dis[to] > dis[from] + e[i].cost)
				{
					dis[to] = dis[from] + e[i].cost;
					pre[to] = from;
					if(!vis[to])
					{
						vis[to] = true;
						q.push(to);
					}
				}
			}
		}
		if(pre[t] == -1)
		{
			return false;
		}
		else
		{
			return true;
		}
	}
	void resole(int s,int t)
	{
		int flow = 0,cost = 0;
		vector<vector<int> > roads_t;
		while(spfa(s,t))
		{
			int min = INF;
			for(int i = t;pre[i] != -1;i = pre[i])
			{
				int from = pre[i],to = i;
				Edge e = deployment.get_edge(from,to);
				if(min > e.cap - e.flow)
				{
					min = e.cap - e.flow;
				}
			}
			vector<int> road;
			road.push_back(min);
			for(int i = t;pre[i] != -1;i = pre[i])
			{
				int from = pre[i],to = i;
				Edge e = deployment.get_edge(from,to);
				e.flow +=min;
				deployment.insert_edge(e);
				if(from != s)
				{
					if(to == t)
					{
						from = consumers_id[from];
					}
					road.push_back(from);
				}

				cost += e.cost*min;
			}
			reverse(road.begin(),road.end());
			roads_t.push_back(road);

#ifdef _LOCAL_DEBUG
			int len = road.size();
			for(int i = 0;i < len;++i)
			{
				// PRINTF(" %d",road[i]);
			}
			// PRINTF("\n");
#endif

			 flow += min;
		}
		roads = roads_t;
		// PRINTF("cost : %d flow : %d\n",cost,flow);
#ifdef _LOCAL_DEBUG
		vector<Edge> e = deployment.get_all_edges();
		int len = e.size();
		for(int i=0;i<len;++i)
		{
			if(e[i].flow != e[i].cap)
			{
				throw runtime_error("e[i].flow != e[i].cap in Result.resole\n");
			}
		}
#endif
	}

	string tostring()
	{
		int line_num = roads.size();
		ostringstream oss;
		oss<<line_num<<endl;
		for(int i = 0;i < line_num;++i)
		{
			oss<<endl;
			vector<int>& road = roads[i];
			int len = road.size();
			oss<<road[0];
			for(int j = 1;j < len;++j)
			{
				oss<<" "<<road[j];
			}
		}
		return oss.str();
	}
	
};





#endif /* RESULT_H_ */
